\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}

\title{Lecture Five -- Linked Lists}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}

\section{Linked Lists}

\subsection{Introduction}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Introduction}}
  Talking about a singly linked list, our author says:
  \begin{quote}
  ``Each element is contained in an object called an \verb'Entry' object,
  that also includes a reference, called a link to the the \verb'Entry'
  object that contains the next element in the list.'' 
  \end{quote}
  --(Collins, page 240)
\end{frame}

\subsection{Singly Linked List}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Singly Linked List}}
  The singly linked list is as defined on the previous slide.  Though
  it is not often seen in `the wild,' the singly linked list serves
  as a nice way to conceptualize a linked list in general.
  \begin{center}\includegraphics[width=8cm]{linkedlist_diag}\newline\end{center}
\end{frame}

\subsection{Doubly Linked List}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Doubly Linked List}}
  The only difference between a singly linked list and doubly linked list
  is that the entries or nodes in a doubly linked list not only have a link
  to the next entry, but also have a linke to the previous entry.
  \begin{center}\includegraphics[width=8cm]{doublylinkedlist}\newline\end{center}
\end{frame}
The interesting property of a doubly linked list is that we can traverse
it both forwards and backwards.  This simplifies some code, for instance, 
node removal.

\subsection{Why two types of lists?}
\begin{frame}[fragile,c]
  \mode<presentation>{\frametitle{Why two types of lists?}}
  \mode<presentation>{\begin{center}Why two types of lists?\end{center}}
\end{frame}
So far we have seen the \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html}{LinkedList}
and the \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html}{ArrayList}.  
Noticing that both implement the \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html}{List}
interface and thus provide the same type of functionality, we may ask ourselves 
how or why we need to choose between the two.


\subsubsection{Sequential vs. Random Access}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Array Lists and Random Access}}
  Array Lists are implemented on top of arrays, and arrays are easy to 
  index into. 
\end{frame}
On many architectures, indexing into an array is just one or two instructions;
it is very cheap and very fast.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Linked Lists and Sequential Access}}
  Accessing linked lists is more `sequential'.
\end{frame}
Notice that if we are accessing the nth item in the linked list, we 
would need to first traverse n-1 elements.  This is quite slow, and 
therefore we see that linked lists are more `sequential' in nature.
However, there are further comparisons to be made.


\subsubsection{Memory Usage}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Memory Usage}}
  \begin{itemize}
    \item Linked lists allocate memory on demand.
    \item Array lists pre-allocate memory in large chunks.
  \end{itemize}
\end{frame}
This is a case where we have to carefully weigh our concerns.
Remember, allocating memory tends to be a somewhat heavy-weight 
operation (this is historically the case...the JVM and/or more sophisticated
malloc techniques may change this arround somewhat).  But there may be
memory-limited environments in which we are willing to trade this time in 
exchange for only as muc memory as we need.

\subsubsection{Insertion and Removal of Elements}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Insertion and Removal of Elements}}
   \begin{itemize}
     \item Very cheap to insert element into the middle of a Linked List.
     \item Much more costly to do this in an Array List.
   \end{itemize}
\end{frame}


\subsection{Iterators in Theory}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Iterators in Theory}}
  An iterator is a ``design pattern'' that ``Provide[s] a way to access
  the elements of an aggregate object sequentially without exposing its
  underlying representation.'' (Gang Of Four, page 257)
  \emph{Requirements}
  \begin{itemize}
    \item We want to access the elements of an arbitrary data 
          structure in order.
    \item We want to do this in the most efficient manner for 
          each data structure.
    \item We want to have a consistent interface across data structures. 
  \end{itemize}
\end{frame}
Though we've said that data structures in general tend to be leaky
abstraction.

\subsection{Iterators in Practice (Java)}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Iterators in Practice (Java)}}
  \begin{itemize}
    \item \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/Iterator.html}{Iterator}
    \item \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/ListIterator.html}{List Iterators}
  \end{itemize}

  Old(ish) way for any Collection:
  \begin{lstlisting}
    LinkedList<BigInteger> myBigIntList = 
                           new LinkedList<BigInteger>();
    Iterator i = myBigIntList.iterator();

    while(i.hasNext()) {
        BigInteger bigInt = i.next();
        System.out.println(o);
    }
  \end{lstlisting}
\end{frame}

\subsection{Are Iterators Still Relevant?}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Are Iterators Still Relevant?}}
  \begin{itemize}
    \item \href{http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Iterable.html}{Iterable}
  \end{itemize}
  \begin{lstlisting}
  LinkedList<BigInteger> myBigIntList = 
                         new LinkedList<BigInteger>();

  for(BigInteger bigInt: myBigIntList) {
     System.out.println(bigInt;
  }
  \end{lstlisting}

Sure! They've just been abstracted away again with some syntactic sugar.
\end{frame}

\end{document}